/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM71 最长上升子序列(一)
 * <a href="https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f?tpId=295&tqId=2281434&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-11-09
 * Time: 21:51
 */

//  动态规划
//LIS：Longest Increasing Subsequence  最长上升子序列
//题目中要求子序列为严格上升的！！！
import java.util.*;

public class Solution {
    public int LIS (int[] arr) {
        int len = arr.length;
        if (len <= 1) {
            return len;
        }
        //dp[i]表示以arr[i]为结尾的严格上升子序列的长度
        int[] dp = new int[len];
        //初始化dp数组为1
        Arrays.fill(dp,1);
        //遍历数组，根据关系进行分别计算
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
            }
        }
        //找出dp数组中的最大值
        int max = dp[0];
        for (int i = 1; i < len; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }
}